package com.test.daily.leetcode.y2022.m06.day0624.home.v01;

import java.util.*;

/**
 * @author Tom on 2022/6/24
 */
public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(3);
        head.left.left = new TreeNode(5);
        head.left.right = new TreeNode(3);
        head.right = new TreeNode(2);
        head.right.right = new TreeNode(9);
        List<Integer> ans = largestValues(head);
        System.out.println(ans);
    }
    public static List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        map.put(root, 0);
        queue.offer(root);
        int curLevel = 0;
        int curMax = Integer.MIN_VALUE;
        while(queue.size() != 0){
            TreeNode cur = queue.poll();
            int level = map.get(cur);
            if(level != curLevel){
                ans.add(curMax);
                curMax = cur.val;
                curLevel = level;
            } else {
                curMax = Math.max(curMax, cur.val);
            }
            if(cur.left != null){
                map.put(cur.left, level+1);
                queue.offer(cur.left);
            }
            if(cur.right != null){
                map.put(cur.right, level+1);
                queue.offer(cur.right);
            }
        }
        ans.add(curMax);
        return ans;
    }
}
